#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<numeric>
#include<cmath>
#include<list>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		vector<long long> oushu;
		vector<long long> jishu;
		for (int i = 0; i < n; i++)
		{
			long long num;
			cin >> num;
			if (num % 2 != 0)
			{
				jishu.push_back(num);
			}
			else
			{
				oushu.push_back(num);
			}
		}
		sort(jishu.begin(), jishu.end());
		sort(oushu.begin(), oushu.end());
		long long ans = 0;
		if (jishu.size() != 0)
		{
			for (int i = 0; i < oushu.size(); i++)
			{
				ans += oushu[i];
			}
			long long temp = jishu.size() / 2;
			for (int i = temp; i < jishu.size(); i++)
			{
				ans += jishu[i];
			}
			cout << ans << endl;
		}
		else
		{
			cout << 0 << endl;
		}
		jishu.clear();
		oushu.clear();
	}
	return 0;
}
